Geographic Information Systems (GIS) are systems for creating, storing, analyzing, and managing geospatial data. GIS manage spatial coordinate data and associated attributes of the coordinate data. GIS typically include a computer system capable of integrating, storing, editing, analyzing, sharing, and displaying geographically-referenced information. GIS allow users to create interactive queries (user created searches), analyze the spatial information, and edit data.
As GIS become distributed and are required to handle larger data volumes, these systems require efficient storage and transport of geographic coordinate data. Efficient storage and transport play an important function in managing large amounts of data on centralized repositories, as well as on small devices where memory is often a limited resource, e.g. mobile phones, handheld devices, GPS navigators, etc. Greater efficiency can be achieved by encoding and compressing the spatial and coordinate data.
Currently, GIS utilize two methods to represent spatial data: raster and vector. Most often, raster data is an image. Vector data uses geometric shapes such as points, lines (series of point, or vertex coordinates), or polygons, to represent objects. For example, freeways may be represented as lines and property boundaries for a housing subdivision may be represented as polygons.
Current popular vector data compression algorithms use predictive coding techniques to compress quantized vertex coordinates. Prediction techniques apply directly to geometry data compression without regard to the geometry coordinates' format, such as GIS binary formats or text/XML documents such as Geography Markup Language (GML).
When using prediction, instead of specifying coordinates, only offsets between predicted and real coordinate values are considered for further coding. Conventionally, encoding two-dimensional (2D) spatial shapes, such as lines and polygons, involves a predictor that takes into consideration only the last or previous vertex in the order of traversal, and considers the predicted vertex to be identical to the previous vertex. This prediction may be termed simple prediction, or delta coding. In simple prediction, the correction transmitted is always the difference between the current and the previous vertex. The simple prediction encoding is attractive because of simplicity in implementation. However, the simplicity reduces the compression rates achieved by simple prediction.